package algorithm.leetcode.online.q2medianoftwosortedarray;

//There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
public class Median {
  public static void main(String[] args){
    int[] a = {};
    int[] b ={2,3};
    System.out.println("median="+median(a,b));
  }
  public static double median(int[] A, int[] B){
    int med, m, n, mi, ni;
    int[] result;
    m = A.length;
    n = B.length;
    result = new int[m+n];
    mi = ni = 0;
    for(int i = 0; i < m + n; i++){
      if(mi < m && ni < n) {
        if(A[mi] < B[ni]){
          result[i] = A[mi];
          mi++;
        }else{
          result[i] = B[ni];
          ni++;
        }

      }else if(mi >= m) {
        result[i] = B[ni];
        ni++;
      }else{
        result[i] = A[mi];
        mi++;
      }
    }
    if((m + n)%2 == 0){
      return (double)(result[(m+n)/2-1] + result[(m+n)/2])/2;
    }else{
      return (double)result[(m+n)/2];
    }
  }
}
